#define _CRT_SECURE_NO_WARNINGS 1

#include "heap.h"

void HeapInit(HP* php)
{
	assert(php);

	php->a = (HPDatatype*)malloc(sizeof(HPDatatype) * N);
	if (php->a == NULL)
	{
		perror("malloc fail\n");
		return;
	}

	php->size = 0;
	php->capacity = N;
}

void HeapInitArray(HP* php,int *a, int n)
{
	assert(php);
	php->a = (HPDatatype*)malloc(sizeof(HPDatatype) * n);
	if (php->a == NULL)
	{
		perror("malloc fail\n");
		return;
	}
	php->size = n;
	php->capacity = n;
	for (int i = 0; i < n; i++)
	{
		php->a[i] = a[i];
	}

	//建大堆
	for(int i=(n-2)/2;i>=0;i--)
	{
		AdjustDownMax(php->a, php->size, i);
	}
	php->size = n;
	php->capacity = n;

}

void HeapDestroy(HP* php)
{
	assert(php);
	free(php->a);
	php->a = NULL;
	php->size = 0;
	php->capacity = 0;

}

void swap(HPDatatype* p1, HPDatatype* p2)
{
	HPDatatype x = *p1;
	*p1 = *p2;
	*p2 = x;
}

//除了child，其他的都是堆
void AdjustUpMax(HPDatatype*a, int child)
{
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		if (a[child] > a[parent])
		{
			swap(&a[child], &a[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}

}

//左右子树都是大/小堆
void AdjustDownMax(HPDatatype* a, int n, int parent)
{
	int child = parent * 2 + 1;
	while (child < n)
	{
		//选出左右子树中大的那一个
		if (child+1<n && a[child + 1]>a[child])   //防止无效数据的出现
		{
			child++;
		}
		if (a[child] > a[parent])
		{
			swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

void HeapPush(HP* php, HPDatatype x)
{
	assert(php);

	if (php->size == php->capacity)
	{
		HPDatatype* temp = (HPDatatype*)realloc(php->a, sizeof(HPDatatype) * php->capacity * 2);
		if (temp == NULL)
		{
			perror("realloc fail\n");
			return;
		}

		php->a = temp;
		php->capacity *= 2;
	}

	php->a[php->size]=x;
	php->size++;

	//向上调整大堆
	AdjustUpMax(php->a, php->size - 1);
}

void HeapPop(HP* php)
{
	assert(php);
	assert(!HeapEmpty(php));

	//堆顶和最后一个结点交换再删除
	swap(&php->a[0], &php->a[php->size - 1]);
	php->size--;

	//向下调整大堆
	AdjustDownMax(php->a, php->size, 0);
}

HPDatatype HeapTop(HP* php)
{
	assert(php);
	return php->a[0];
}

bool HeapEmpty(HP* php)
{
	assert(php);
	return php->size == 0;
}

int HeapSize(HP* php)
{
	assert(php);
	return php->size;
}

void AdjustDownMin(HPDatatype* a, int n, int parent)
{
	int child = parent * 2 + 1;
	while (child < n)
	{
		//选出左右子树中小的那一个
		if (child + 1 < n && a[child + 1] < a[child])   //防止无效数据的出现
		{
			child++;
		}
		if (a[child] < a[parent])
		{
			swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

void AdjustUpMin(HPDatatype* a, int child)
{
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		if (a[child] < a[parent])
		{
			swap(&a[child], &a[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}